import com.sun.source.tree.Tree;

public class BinarySearchTree {
    public TreeNode root;

    public void insertTreeNode(int val) {
        if (root == null) root = new TreeNode(val);
        else {
            TreeNode node = new TreeNode(val);
            TreeNode parent = root;
            TreeNode cur = root;
            while (cur != null) {
                if (node.val < cur.val) {
                    parent = cur;
                    cur = cur.left;
                } else if (node.val > cur.val) {
                    parent = cur;
                    cur = cur.right;
                } else {
                    return;
                }
            }
            if (parent.val > node.val) {
                parent.left = node;
            } else {
                parent.right = node;
            }
        }
    }

    public TreeNode searchTreeNode(int val) {
        if (root == null) return null;
        if (val == root.val) return root;
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val > val) {
                cur = cur.left;
            } else if (cur.val < val) {
                cur = cur.right;
            } else {
                return cur;
            }
        }
        return null;
    }

    public void removeTreeNode(int val) {
        if (root == null) return;
        TreeNode cur = root;
        TreeNode parent = root;
        //cur.left==null
        while (cur != null) {
            if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else {
                remove(cur, parent);
            }
        }

    }

    private void remove(TreeNode cur, TreeNode parent) {
        if (cur.left == null) {
            if (cur.val == root.val) {
                root = cur.right;
            } else if (cur == parent.left) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
            if (cur.val == root.val) {
                root = cur.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            }else{
                parent.right = cur.left;
            }
        }else{
            TreeNode tp=cur;
            TreeNode t=cur.right;
            while(t.left!=null) {
                tp=t;
                t=t.left;
            }
            cur.val=t.val;
            if(tp.left==t){
                tp.left=t.right;
            }else{
                tp.right=t.right;
            }
        }
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

}
